// 被围绕的区域： https://leetcode-cn.com/problems/surrounded-regions/

// copy函数这块，只有值传递 go: 耽误了不少事儿： https://blog.csdn.net/pythonstrat/article/details/120721534

package main

func solve(board [][]byte)  {
	// 1. 复制一份 board
	n, m := len(board), len(board[0])
	b := make([][]byte, n)
	for i, _ := range b {
		temp := make([]byte, m)
		copy(temp, board[i])
		b[i] = temp
	}

	// 2. dfs
	dir := [][2]int{{0, -1}, {0, 1}, {1, 0}, {-1, 0}}
	var dfs func(x, y int)

	dfs = func(x, y int) {
		if b[x][y] == 'X'{
			return
		}

		// 有边界
		b[x][y] = 'X'

		for _, ac := range dir {
			newX := ac[0] + x
			newY := ac[1] + y
			// 剪枝
			if newX >= 0 && newY >= 0 &&
				newX < n && newY < m {
				dfs(newX, newY)
			}
		}
	}

	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			// 遍历四个边
			if i == 0 || i == n - 1 ||
				j == 0 || j == m - 1 {
				if b[i][j] == 'O' {
					// 调用深度优先遍历，找到这一块陆地
					dfs(i, j)
				}
			}
		}
	}

	// 填充board
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if b[i][j] == 'O' {
				board[i][j] = 'X'
			}
		}
	}
}
